class Solution:
    def romanToInt(self, s: str) -> int:
        d = {'I': 1, 'IV': 4, 'V': 5, 'IX': 9, 'X': 10, 'XL': 40, 'L': 50, 'XC': 90, 'C': 100, 'CD': 400, 'D': 500,
             'CM': 900, 'M': 1000}
        result = 0
        i = 0
        while i < len(s):
            # print(len(s))
            # 查看当前位和下一位的字符
            str1 = s[i:i + 2]
            print(str1)
            # 如果当前位置是特殊情况，那么返回其在字典中对应值，并且下一次从特殊字符之后一位开始索引
            if str1 in d:
                result += d.get(str1)
                i += 2
                print('第一种情况的', result)
            # 如果当前位不是特殊情况，那么只返回当前位的数值
            else:
                result += d[s[i]]
                print('第二种情况的', result)
                i += 1
        return result

    def lengthOfLastWord(self, s: str) -> int:
        a = s.strip(' ')
        a = a.split(' ')
        b = len(a)
        c = a[b - 1]

        return len(c)

    def plusOne(self, digits):
        n = ''
        num = []
        for i in digits:
            n += str(i)
        n = int(n) + 1
        for j in str(n):
            num.append(int(j))
        return num

    def addBinary(self, a: str, b: str) -> str:
        return bin(int(a, 2) + int(b, 2))[2:]

    def mySqrt(self, x: int) -> int:
        l, r, ans = 0, x, -1
        while l <= r:
            print("l值为：", l)
            print("r值为：", r)
            mid = (l + r) // 2
            print("mid值为：", mid)
            if mid * mid <= x:
                ans = mid
                l = mid + 1
            else:
                r = mid - 1
        return ans

    def deleteDuplicates(self, head):
        if head is None or head.next is None: return head
        cur, next = head, head.next
        print(cur)
        print(next)
        while next:
            if next.val != cur.val:
                cur = cur.next
            else:
                cur.next = next.next
            next = next.next

        return head

    def merge(self, nums1, m: int, nums2, n):
        """
        Do not return anything, modify nums1 in-place instead.
        """
        k = m + n - 1
        while m > 0 and n > 0:
            if nums1[m - 1] > nums2[n - 1]:
                nums1[k] = nums1[m - 1]
                m -= 1
            else:
                nums1[k] = nums2[n - 1]
                n -= 1
            k -= 1
        nums1[:n] = nums2[:n]

    def isSymmetric(self, root) -> bool:
        if not root:
            return True

        def dfs(left, right):
            if not (left or right):
                return True
            if not (left and right):
                return False
            if left.val != right.val:
                return False
            return dfs(left.left, right.right) and dfs(left.right, right.left)

        return dfs(root.left, root.right)

    def maxProfit(self, prices):
        minprice = float('inf')  # 所有数都比 +inf 小
        print(minprice)
        maxprofit = 0
        for price in prices:
            minprice = min(minprice, price)
            print(minprice)
            maxprofit = max(maxprofit, price - minprice)
        return maxprofit

    def hasPathSum(self, root, sum):
        if not root:
            return False
        if not root.left and not root.right:
            return sum == root.val

        return self.hasPathSum(root.left, sum - root.val) or self.hasPathSum(root.right, sum - root.val)


if __name__ == '__main__':
    a = Solution()
    print(a.maxProfit([1, 2, 3, 4, 9]))
